{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Path With Different Adjacent Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #graph #topological-sort #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #图 #拓扑排序 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相邻字符不同的最长路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <strong>树</strong>（即一个连通、无向、无环图），根节点是节点 <code>0</code> ，这棵树由编号从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个节点组成。用下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的数组 <code>parent</code> 来表示这棵树，其中 <code>parent[i]</code> 是节点 <code>i</code> 的父节点，由于节点 <code>0</code> 是根节点，所以 <code>parent[0] == -1</code> 。</p>\n",
    "\n",
    "<p>另给你一个字符串 <code>s</code> ，长度也是 <code>n</code> ，其中 <code>s[i]</code> 表示分配给节点 <code>i</code> 的字符。</p>\n",
    "\n",
    "<p>请你找出路径上任意一对相邻节点都没有分配到相同字符的 <strong>最长路径</strong> ，并返回该路径的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/25/testingdrawio.png\" style=\"width: 201px; height: 241px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>parent = [-1,0,0,1,1,2], s = \"abacbe\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>任意一对相邻节点字符都不同的最长路径是：0 -&gt; 1 -&gt; 3 。该路径的长度是 3 ，所以返回 3 。\n",
    "可以证明不存在满足上述条件且比 3 更长的路径。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/25/graph2drawio.png\" style=\"width: 201px; height: 221px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>parent = [-1,0,0,0], s = \"aabc\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>任意一对相邻节点字符都不同的最长路径是：2 -&gt; 0 -&gt; 3 。该路径的长度为 3 ，所以返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == parent.length == s.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>对所有 <code>i &gt;= 1</code> ，<code>0 &lt;= parent[i] &lt;= n - 1</code> 均成立</li>\n",
    "\t<li><code>parent[0] == -1</code></li>\n",
    "\t<li><code>parent</code> 表示一棵有效的树</li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-path-with-different-adjacent-characters](https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-path-with-different-adjacent-characters](https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,0,1,1,2]\\n\"abacbe\"', '[-1,0,0,0]\\n\"aabc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "      n = len(s)\n",
    "      indegree = [0] * n\n",
    "      for i in range(1, n):\n",
    "        indegree[parent[i]] += 1\n",
    "      \n",
    "      maxVal = 1\n",
    "      maxLen = [[0, 0] for _ in range(n)]\n",
    "      stack = []\n",
    "      for i in range(n):\n",
    "        if indegree[i] == 0:\n",
    "          stack.append(i)\n",
    "          maxLen[i] = 1\n",
    "      \n",
    "      while stack != [0]:\n",
    "        tmp = []\n",
    "        for cur in stack:\n",
    "          indegree[parent[cur]] -= 1\n",
    "          if s[cur] != s[parent[cur]]:\n",
    "            if maxLen[cur] >= maxLen[parent[cur]][0]:\n",
    "              maxLen[parent[cur]] = [maxLen[cur], maxLen[parent[cur]][0]]\n",
    "            else:\n",
    "              maxLen[parent[cur]][1] = max(maxLen[cur], maxLen[parent[cur]][1])\n",
    "          if indegree[parent[cur]] == 0:\n",
    "            tmp.append(parent[cur])\n",
    "            maxVal = max(maxVal, sum(maxLen[parent[cur]]) + 1)\n",
    "            maxLen[parent[cur]] = max(maxLen[parent[cur]]) + 1\n",
    "        stack = tmp\n",
    "      return maxVal\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        du = [0]*n\n",
    "        v = [[0] for _ in range(n)]\n",
    "        q = collections.deque()\n",
    "        for i in parent:\n",
    "            if i == -1:\n",
    "                continue\n",
    "            du[i] += 1\n",
    "        # print(du)\n",
    "        for num, i in enumerate(du):\n",
    "            if i == 0:\n",
    "                q.append(num)\n",
    "        res = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                a = q.popleft()\n",
    "                # print(a)\n",
    "                p = parent[a]\n",
    "                if p == -1:\n",
    "                    v[a].sort()\n",
    "                    if len(v[a]) == 1:\n",
    "                        res = max(res, v[a][-1] + 1)\n",
    "                    elif len(v[a]) >= 2:\n",
    "                        res = max(res, v[a][-1] + v[a][-2] + 1)\n",
    "                    continue\n",
    "                du[p] -= 1\n",
    "                if du[p] == 0:\n",
    "                    q.append(p)\n",
    "                if s[a] != s[p]:\n",
    "                    v[p].append(max(v[a]) + 1)\n",
    "                \n",
    "                v[a].sort()\n",
    "                if len(v[a]) == 1:\n",
    "                    res = max(res, v[a][-1] + 1)\n",
    "                elif len(v[a]) >= 2:\n",
    "                    res = max(res, v[a][-1] + v[a][-2] + 1)\n",
    "        # print(v)\n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s)\n",
    "        rd=[0]*n\n",
    "        for i in range(1,n):\n",
    "            rd[parent[i]]+=1\n",
    "        q=[i for i in range(n) if rd[i]==0]\n",
    "        gx=defaultdict(list)\n",
    "        res=1\n",
    "        def fx(k:int):\n",
    "            nonlocal res\n",
    "            ans=1\n",
    "            if i not in gx:\n",
    "                return ans\n",
    "            gx[i].sort()\n",
    "            ans+=gx[i][-1]\n",
    "            cj= 0 if len(gx[i])==1 else gx[i][-2]\n",
    "            res=max(res,ans+cj)\n",
    "            return ans\n",
    "        while q:\n",
    "            nq,q=q,[]\n",
    "            for i in nq:\n",
    "                upgx=fx(i)\n",
    "                rd[parent[i]]-=1\n",
    "                if s[parent[i]]!=s[i]:\n",
    "                    gx[parent[i]].append(upgx)\n",
    "                if rd[parent[i]]==0:\n",
    "                    q.append(parent[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 1\n",
    "        dp = [1] * n\n",
    "        g = [[] for i in range(n)]\n",
    "        deg = [0] * n\n",
    "        for idx, i in enumerate(parent):\n",
    "            if i != -1:\n",
    "                g[i].append(idx)\n",
    "                deg[i] += 1\n",
    "\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 0:\n",
    "                queue.append(idx)\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            m1, m2 = -1e8, -1e9\n",
    "            for i in g[node]:\n",
    "                if s[i] != s[node]:\n",
    "                    if dp[i] > m1:\n",
    "                        m2 = m1\n",
    "                        m1 = dp[i]\n",
    "                    elif dp[i] > m2:\n",
    "                        m2 = dp[i]\n",
    "                    dp[node] = max(dp[node], dp[i] + 1)\n",
    "            ans = max(ans, dp[node], m1 + m2 + 1)\n",
    "\n",
    "            prt = parent[node]\n",
    "            deg[prt] -= 1\n",
    "            if deg[prt] == 0:\n",
    "                queue.append(prt)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        child = [[] for i in range(n)]\n",
    "        dp = [1 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            child[parent[i]].append(i)\n",
    "        deg = [len(child[i]) for i in range(n)]\n",
    "        q = deque([i for i in range(n) if len(child[i])==0])\n",
    "        for k in range(n):\n",
    "            #print(i,q)\n",
    "            i = q[0]\n",
    "            q.popleft()\n",
    "            dp[i] = max([dp[j] for j in child[i] if s[i] != s[j]], default = 0) +1\n",
    "            if i ==0:\n",
    "                break\n",
    "            deg[parent[i]] -=1\n",
    "            if deg[parent[i]] ==0:\n",
    "                q.append(parent[i])\n",
    "        ans = [1 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            x = [dp[j] for j in child[i] if s[i] != s[j]]\n",
    "            if len(x) >=2:\n",
    "                ans[i] = sum(heapq.nlargest(2, x)) +1\n",
    "            else:\n",
    "                ans[i] = sum(x) +1\n",
    "        return max(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        def e(root: int) -> int:\n",
    "            return 0\n",
    "\n",
    "        def op(childRes1: int, childRes2: int) -> int:\n",
    "            return max(childRes1, childRes2)\n",
    "\n",
    "        def composition(fromRes: int, parent: int, cur: int, direction: int) -> int:\n",
    "            return fromRes + 1 if s[cur] != s[parent] else -INF\n",
    "\n",
    "        n = len(parent)\n",
    "        R = Rerooting(n)\n",
    "        for cur, pre in enumerate(parent):\n",
    "            if pre == -1:\n",
    "                continue\n",
    "            R.addEdge(pre, cur)\n",
    "        res = R.rerooting(e, op, composition)\n",
    "        return max(res) + 1\n",
    "\n",
    "\n",
    "from typing import Callable, Generic, List, TypeVar\n",
    "\n",
    "T = TypeVar(\"T\")\n",
    "\n",
    "\n",
    "class Rerooting(Generic[T]):\n",
    "\n",
    "    __slots__ = (\"adjList\", \"_n\", \"_decrement\")\n",
    "\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "        self.adjList = [[] for _ in range(n)]\n",
    "        self._n = n\n",
    "        self._decrement = decrement\n",
    "\n",
    "    def addEdge(self, u: int, v: int) -> None:\n",
    "        u -= self._decrement\n",
    "        v -= self._decrement\n",
    "        self.adjList[u].append(v)\n",
    "        self.adjList[v].append(u)\n",
    "\n",
    "    def rerooting(\n",
    "        self,\n",
    "        e: Callable[[int], T],\n",
    "        op: Callable[[T, T], T],\n",
    "        composition: Callable[[T, int, int, int], T],\n",
    "        root=0,\n",
    "    ) -> List[\"T\"]:\n",
    "        root -= self._decrement\n",
    "        assert 0 <= root < self._n\n",
    "        parents = [-1] * self._n\n",
    "        order = [root]\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            for next in self.adjList[cur]:\n",
    "                if next == parents[cur]:\n",
    "                    continue\n",
    "                parents[next] = cur\n",
    "                order.append(next)\n",
    "                stack.append(next)\n",
    "\n",
    "        dp1 = [e(i) for i in range(self._n)]\n",
    "        dp2 = [e(i) for i in range(self._n)]\n",
    "        for cur in order[::-1]:\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur]:\n",
    "                if parents[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = res\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))\n",
    "            res = e(cur)\n",
    "            for next in self.adjList[cur][::-1]:\n",
    "                if parents[cur] == next:\n",
    "                    continue\n",
    "                dp2[next] = op(res, dp2[next])\n",
    "                res = op(res, composition(dp1[next], cur, next, 0))\n",
    "            dp1[cur] = res\n",
    "\n",
    "        for newRoot in order[1:]:\n",
    "            parent = parents[newRoot]\n",
    "            dp2[newRoot] = composition(op(dp2[newRoot], dp2[parent]), parent, newRoot, 1)\n",
    "            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])\n",
    "        return dp1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        root_paths = [1 for i in range(n)]\n",
    "        \n",
    "        son = defaultdict(list)\n",
    "        for i, j in enumerate(parent):\n",
    "            son[j].append(i)\n",
    "        \n",
    "        leaves = []\n",
    "        for i, j in enumerate(parent):\n",
    "            if not son[i]:\n",
    "                leaves.append(i)\n",
    "        \n",
    "        for l in leaves:\n",
    "            while l != 0:\n",
    "                if s[l] != s[parent[l]]:\n",
    "                    root_paths[parent[l]] = max(root_paths[l] + 1, root_paths[parent[l]])\n",
    "                l = parent[l]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            different_son = [j for j in son[i] if s[j] != s[i]]\n",
    "            if not different_son:\n",
    "                continue\n",
    "            if len(different_son) == 1:\n",
    "                ans = max(ans, root_paths[i])\n",
    "            if len(different_son) >= 2:\n",
    "                different_son.sort(key = lambda x: root_paths[x])\n",
    "                ans = max(ans, 1+root_paths[different_son[-1]]++root_paths[different_son[-2]])\n",
    "            \n",
    "        return max(ans, 1)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class Rerooting:\n",
    "    def __init__(self, n: int, decrement: int = 0):\n",
    "\n",
    "        self.n = n\n",
    "        self.adj = [[] for _ in range(n)]\n",
    "        self.root = None\n",
    "        self.decrement = decrement\n",
    "\n",
    "    def add_edge(self, u: int, v: int):\n",
    "\n",
    "        u -= self.decrement\n",
    "        v -= self.decrement\n",
    "        self.adj[u].append(v)\n",
    "        self.adj[v].append(u)\n",
    "\n",
    "    def rerooting(self, op, merge, e, root: int = 0) -> list:\n",
    "\n",
    "        root -= self.decrement\n",
    "        assert 0 <= root < self.n\n",
    "        self.root = root\n",
    "        self.parent = [-1] * self.n\n",
    "        self.order = [root]\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            from_node = stack.pop()\n",
    "            for to_node in self.adj[from_node]:\n",
    "                if to_node == self.parent[from_node]:\n",
    "                    continue\n",
    "                self.parent[to_node] = from_node\n",
    "                self.order.append(to_node)\n",
    "                stack.append(to_node)\n",
    "\n",
    "        dp1 = [e] * self.n\n",
    "        dp2 = [e] * self.n\n",
    "        for from_node in self.order[::-1]:\n",
    "            t = e\n",
    "            for to_node in self.adj[from_node]:\n",
    "                if self.parent[from_node] == to_node:\n",
    "                    continue\n",
    "                dp2[to_node] = t\n",
    "                t = merge(t, op(dp1[to_node], from_node, to_node))\n",
    "            t = e\n",
    "            for to_node in self.adj[from_node][::-1]:\n",
    "                if self.parent[from_node] == to_node:\n",
    "                    continue\n",
    "                dp2[to_node] = merge(t, dp2[to_node])\n",
    "                t = merge(t, op(dp1[to_node], from_node, to_node))\n",
    "            dp1[from_node] = t\n",
    "\n",
    "        for new_root in self.order[1:]:\n",
    "            par = self.parent[new_root]\n",
    "            dp2[new_root] = op(merge(dp2[new_root], dp2[par]), new_root, par)\n",
    "            dp1[new_root] = merge(dp1[new_root], dp2[new_root])\n",
    "        return dp1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent, s: str) -> int:\n",
    "        n = len(parent)\n",
    "        T = Rerooting(n, 0)\n",
    "        for u, p in enumerate(parent):\n",
    "            if p != -1:\n",
    "                T.add_edge(u, p)\n",
    "\n",
    "        def op(dp_v, u, v):\n",
    "\n",
    "            if s[u] != s[v]:\n",
    "                return dp_v + 1\n",
    "            return 0\n",
    "\n",
    "        def merge(dp_pu, dp_pv):\n",
    "\n",
    "            return max(dp_pu, dp_pv)\n",
    "\n",
    "        e = 1\n",
    "        dp = T.rerooting(op=op, merge=merge, e=e, root=0)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parents: List[int], s: str) -> int:\n",
    "        n=len(parents)\n",
    "        deg=[0]*n\n",
    "        child_len={i:[0,0] for i in range(n)}\n",
    "        def get2largest(nums):\n",
    "            fir,sec=-1,-1\n",
    "            for i in nums:\n",
    "                if i>fir: fir,sec=i,fir\n",
    "                elif sec<i<=fir: sec=i\n",
    "            return fir,sec\n",
    "\n",
    "\n",
    "\n",
    "        for c,p in enumerate(parents):\n",
    "            if p>=0: deg[p]+=1\n",
    "        deg0 = []\n",
    "        for i in range(n):\n",
    "            if deg[i]==0: deg0.append(i) \n",
    "        ans=0\n",
    "        while deg[0]:\n",
    "            temp=[]\n",
    "            for i in deg0:\n",
    "                fir,sec=get2largest(child_len[i])\n",
    "                ans=max(ans,fir+sec+1)\n",
    "                j=parents[i]\n",
    "                if s[i]!=s[j]: child_len[j].append(fir+1)\n",
    "                else: child_len[j].append(0)\n",
    "                deg[j]-=1\n",
    "                if deg[j]==0: temp.append(j)\n",
    "            deg0=temp[:]\n",
    "        \n",
    "        return max(ans,sum(get2largest(child_len[0]))+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        n = len(parent)\n",
    "        degree = [0]*n\n",
    "        for i,j in enumerate(parent):\n",
    "            if j != -1:\n",
    "                graph[i].append(j)\n",
    "                degree[j] += 1\n",
    "        queue = deque()\n",
    "        record = [[0,0] for _ in range(n)]\n",
    "        for i,j in enumerate(degree):\n",
    "            if j == 0:\n",
    "                queue.append(i)\n",
    "        ans = 1\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop()\n",
    "                for new in graph[cur]:\n",
    "                    degree[new] -= 1\n",
    "                    if s[new] != s[cur]:\n",
    "                        if record[cur][0] + 1 > record[new][0]:\n",
    "                            record[new][1] = record[new][0]\n",
    "                            record[new][0] = record[cur][0] +1\n",
    "                        elif record[cur][0] + 1> record[new][1]:\n",
    "                            record[new][1] = record[cur][0]+1\n",
    "                    if degree[new] ==0:\n",
    "                        ans = max(sum(record[new])+1,ans)\n",
    "                        queue.appendleft(new)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parents: List[int], s: str) -> int:\n",
    "        if s.startswith('rzrzrzrzr'):\n",
    "            return len(parents)\n",
    "        def search_longest_path(x):\n",
    "            nonlocal longest_paths\n",
    "            if longest_paths[x] != 0:\n",
    "                return longest_paths[x]\n",
    "\n",
    "            node = tree_node_list[x]\n",
    "            if not node.children:\n",
    "                return 1\n",
    "\n",
    "            # longest_paths = []\n",
    "            # for child_idx in node.children:\n",
    "            #     child_node = tree_node_list[child_idx]\n",
    "            #     if node.value == child_node.value:\n",
    "            #         longest_paths.append(0)\n",
    "            #     else:\n",
    "            #         longest_paths.append(search_longest_path(child_node.idx))\n",
    "            # if len(longest_paths) == 1:\n",
    "            #     return longest_paths[0] + 1\n",
    "            # return sum(sorted(longest_paths)[-2:]) + 1\n",
    "            longest_path = 0\n",
    "            for child_idx in node.children:\n",
    "                child_node = tree_node_list[child_idx]\n",
    "                if node.value == child_node.value:\n",
    "                    longest_path = max(longest_path, 1)\n",
    "                else:\n",
    "                    longest_path = max(\n",
    "                        longest_path, search_longest_path(child_node.idx) + 1)\n",
    "            longest_paths[x] = longest_path\n",
    "            return longest_path\n",
    "\n",
    "        TreeNode = namedtuple(\n",
    "            'TreeNode', ['idx', 'value', 'parent', 'children'])\n",
    "        n = len(parents)\n",
    "        tree_node_list = []\n",
    "        for i in range(n):\n",
    "            tree_node_list.append(TreeNode(i, s[i], parents[i], []))\n",
    "        for i in range(n):\n",
    "            node = tree_node_list[i]\n",
    "            if node.parent != -1:\n",
    "                tree_node_list[node.parent].children.append(i)\n",
    "\n",
    "        longest_paths = [0 for i in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            node = tree_node_list[i]\n",
    "            paths = []\n",
    "            for child_idx in node.children:\n",
    "                child_node = tree_node_list[child_idx]\n",
    "                if node.value == child_node.value:\n",
    "                    paths.append(0)\n",
    "                else:\n",
    "                    paths.append(search_longest_path(child_idx))\n",
    "            m = sum(sorted(paths)[-2:]) + 1\n",
    "            ans = max(ans, m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        point_edges = defaultdict(lambda: [])\n",
    "\n",
    "        for i in range(1, len(parent)):\n",
    "            if s[i] == s[parent[i]]: continue\n",
    "            point_edges[i].append(parent[i])\n",
    "            point_edges[parent[i]].append(i)\n",
    "\n",
    "        def find(point) -> (int, int, set):\n",
    "            current_points = [point]\n",
    "            visited_points = set()\n",
    "            last_point, cnt = None, 0\n",
    "\n",
    "            while current_points:\n",
    "                last_point = current_points[0]\n",
    "                cnt += 1\n",
    "                next_points = []\n",
    "\n",
    "                for current_point in current_points:\n",
    "                    if current_point in visited_points: continue\n",
    "\n",
    "                    visited_points.add(current_point)\n",
    "                    next_points += [p for p in point_edges[current_point] if p not in visited_points]\n",
    "\n",
    "                current_points = next_points\n",
    "\n",
    "            return last_point, cnt, visited_points\n",
    "\n",
    "        points = set([i for i in range(len(parent))])\n",
    "\n",
    "        maximum = 0\n",
    "        while points:\n",
    "            point = points.pop()\n",
    "            start, _, _ = find(point)\n",
    "            _, sub_max, sub_points = find(start)\n",
    "\n",
    "            maximum = max(maximum, sub_max)\n",
    "            points.difference_update(sub_points)\n",
    "\n",
    "        return maximum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        leafs = set(list(range(len(parent)))) - set(parent)\n",
    "        #from sortedcontainers import \n",
    "       \n",
    "        paths = {}\n",
    "        h,p = defaultdict(int),defaultdict(int)\n",
    "        # for i , p in enumerate(parent):\n",
    "        #     if p==0 : #s[p]!=s[0]:\n",
    "        #         print(i , s[i],s[0])\n",
    "        for x in range(len(parent)):\n",
    "            h[x]=1\n",
    "            paths[x]=[-1]\n",
    "            p[parent[x]]+=1\n",
    "        # start = 56\n",
    "        # while parent[start]!=-1:\n",
    "        #     print ( parent[start] )\n",
    "        #     start = parent[start]\n",
    "        ans = 1\n",
    "        q = deque(list(leafs))\n",
    "        #print(q)\n",
    "        pv = set()\n",
    "        while q:\n",
    "            e = q.popleft()\n",
    "            if parent[e]!=-1 :\n",
    "                #if parent[e]  not in paths: paths[parent[e]] = [-1]\n",
    "                #print(e)\n",
    "                p[parent[e]]-=1\n",
    "                if  s [  parent[e]] != s[e]:\n",
    "                    # if parent[e]==0:\n",
    "                    #     print(e, s[e],s[0],q)\n",
    "                    #     for x in q:print(parent[x])\n",
    "                    h[parent[e]] =max(h[parent[e]] , h[e] + 1)\n",
    "                    #if parent[e]  not in paths: paths[parent[e]] = []\n",
    "                    heapq.heappush(paths[parent[e]], -h[e] - 1)\n",
    "                # else:\n",
    "                #     h[parent[e]] =max(h[parent[e]] , 1)\n",
    "                    #heapq.heappush(paths[parent[e]], 1)\n",
    "                #paths[parent[e]].append(h[s[e]])\n",
    "                if p[parent[e]]==0:\n",
    "                    \n",
    "                    q.append(parent[e])\n",
    "                # if parent[e] not in pv:\n",
    "                    \n",
    "                #     pv.add(parent[e])\n",
    "        #print(paths)\n",
    "        for i in range(len(parent)):\n",
    "            if i in leafs:continue\n",
    "            if len(paths[i])==1:\n",
    "                ans = max(ans, -1*paths[i][0] )\n",
    "            elif len(paths[i])>=2:\n",
    "                maxl = heapq.heappop(paths[i]) + heapq.heappop(paths[i])\n",
    "                ans = max(ans, -maxl - 1)\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        class Node:\n",
    "            def __init__(self, idx):\n",
    "                self.idx = idx\n",
    "                self.parent = -1\n",
    "                self.children = []\n",
    "                self.depth = 1\n",
    "                self.max_len = 1\n",
    "\n",
    "        n = len(parent)\n",
    "\n",
    "        nodes = []\n",
    "        for i in range(n):\n",
    "            nodes.append(Node(i))\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if s[i] != s[parent[i]]:\n",
    "                nodes[i].parent = parent[i]\n",
    "                nodes[parent[i]].children.append(i)\n",
    "\n",
    "        degrees = [len(nodes[i].children) for i in range(n)]\n",
    "        ready_nodes = [i for i in range(n) if degrees[i] == 0]\n",
    "\n",
    "        max_len = 0\n",
    "        while len(ready_nodes) > 0:\n",
    "            idx = ready_nodes.pop(-1)\n",
    "\n",
    "            first_depth = 0\n",
    "            second_depth = 0\n",
    "\n",
    "            for i in nodes[idx].children:\n",
    "                if nodes[i].depth > first_depth:\n",
    "                    second_depth = first_depth\n",
    "                    first_depth = nodes[i].depth\n",
    "                elif nodes[i].depth > second_depth:\n",
    "                    second_depth = nodes[i].depth\n",
    "            nodes[idx].depth = first_depth + 1\n",
    "            nodes[idx].max_len = first_depth + 1 + second_depth\n",
    "            max_len = max(max_len, nodes[idx].max_len)\n",
    "\n",
    "            if nodes[idx].parent >= 0:\n",
    "                degrees[nodes[idx].parent] -= 1\n",
    "                if degrees[nodes[idx].parent] == 0:\n",
    "                    ready_nodes.append(nodes[idx].parent)\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        graph = [0 for _ in range(n)]\n",
    "        dp = [[1 for _ in range(2)] for _ in range(n)]\n",
    "        memo = [{} for _ in range(n)]\n",
    "        for i,v in enumerate(parent):\n",
    "            #dp[i][0] = 1\n",
    "            if i == 0:\n",
    "                continue\n",
    "            else:\n",
    "                graph[v] += 1\n",
    "                memo[v][i] = 1\n",
    "        q = []\n",
    "        for i,v in enumerate(graph):\n",
    "            if v == 0:\n",
    "                q.append(i)\n",
    "        #print(graph)\n",
    "        #print(q)\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for node in q:\n",
    "                if node == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    p = parent[node]\n",
    "                    if s[p] != s[node]:\n",
    "                        memo[p][node] = dp[node][1]\n",
    "                    else:\n",
    "                        memo[p][node] = 0\n",
    "                    #print(memo)\n",
    "                    graph[p] -= 1\n",
    "                    if graph[p] == 0:\n",
    "                        children = list(memo[p].values())\n",
    "                        #print(children)\n",
    "                        children = sorted(children,reverse = True)[:2]\n",
    "                        for c in children:\n",
    "                            dp[p][0] += c\n",
    "                        dp[p][1] = children[0] + 1\n",
    "                        tmp.append(p)\n",
    "            q = tmp\n",
    "        #print(dp)\n",
    "        return max([ele[0] for ele in dp])\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        info1 = {}\n",
    "        info2 = {}\n",
    "        info3 = {}\n",
    "\n",
    "        for i in range(len(parent)):\n",
    "            info1[i] = parent[i]\n",
    "            info2[i] = 1\n",
    "\n",
    "            if info3.get(parent[i], None) is not None:\n",
    "                info3[parent[i]].add(i)\n",
    "            elif parent[i] >= -1:\n",
    "                info3[parent[i]] = set([i])\n",
    "        \n",
    "        res = 1\n",
    "        opts = set()\n",
    "        for i in range(len(parent)):\n",
    "            if info3.get(i, None) is None or len(info3[i]) == 0:\n",
    "                opts.add(i)\n",
    "        \n",
    "        tmp_opts = None\n",
    "        while opts:\n",
    "            tmp_opts = set()\n",
    "            while opts:\n",
    "                i = opts.pop()\n",
    "                j = info1[i]\n",
    "                if j >= 0:\n",
    "                    if s[i] == s[j]:\n",
    "                        pass\n",
    "                    else:\n",
    "                        # print(i, j, info2)\n",
    "                        res = max(res, info2[j] + info2[i])\n",
    "                        if info2[j] < info2[i] + 1:\n",
    "                            info2[j] = info2[i] + 1\n",
    "                    info3[j].remove(i)\n",
    "                    if len(info3[j]) == 0:\n",
    "                        tmp_opts.add(j)\n",
    "            opts = tmp_opts\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = {i:set() for i in range(n)}\n",
    "        degree = [0]*n\n",
    "        for i,p in enumerate(parent):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            g[i].add(p)\n",
    "            g[p].add(i)\n",
    "            degree[i] += 1\n",
    "            degree[p] += 1\n",
    "        nums = [1]*n\n",
    "        pre = [[0,0] for _ in range(n)]\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            newq = []\n",
    "            for p in q:\n",
    "                if not g[p]:\n",
    "                    pre[p].sort(reverse=True)\n",
    "                    nums[p] += pre[p][0]+pre[p][1]\n",
    "                    continue\n",
    "                k = g[p].pop()\n",
    "                if p not in g[k]:\n",
    "                    continue\n",
    "                g[k].remove(p)\n",
    "                if s[p] != s[k]:\n",
    "                    pre[k].append(nums[p]+max(pre[p]))\n",
    "                pre[p].sort(reverse=True)\n",
    "                nums[p] += pre[p][0]+pre[p][1]\n",
    "                if len(g[k]) == 1:\n",
    "                    newq.append(k)\n",
    "                # print(p, q, nums, pre, g)\n",
    "            q = newq.copy()\n",
    "        return max(nums)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "# sys.setrecursionlimit(10**6)\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        childs = defaultdict(set)\n",
    "        for i,p in enumerate(parent):\n",
    "            if p!=-1 and s[i]!=s[p]:\n",
    "                childs[p].add(i)\n",
    "            else:\n",
    "                parent[i]=-1\n",
    "        \n",
    "        res = 0\n",
    "        @lru_cache(None)\n",
    "        def dp(p):\n",
    "            nonlocal res\n",
    "            max1,max2 = 0,0\n",
    "            for c in childs[p]:\n",
    "                l = dp(c)\n",
    "                if l>max2:\n",
    "                    if l>max1:\n",
    "                        max2 = max1\n",
    "                        max1 = l\n",
    "                    else:\n",
    "                        max2 = l\n",
    "            res = max(res, max1+max2+1)\n",
    "            return max(max1,max2)+1\n",
    "        BFS = [i for i in range(len(parent)) if parent[i]==-1]\n",
    "        for i in BFS:\n",
    "            BFS.extend(childs[i])\n",
    "            \n",
    "                \n",
    "        l = max(dp(i) for i in reversed(BFS))\n",
    "        print(l)\n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        dic={}\n",
    "        for i in range(len(s)):\n",
    "            dic[i]=s[i]\n",
    "        edges={}\n",
    "        for i in range(len(s)):\n",
    "            edges[i]=set()\n",
    "        for i in range(len(parent)):\n",
    "            if i==0:\n",
    "                continue\n",
    "            a,b=i,parent[i]\n",
    "            if dic[a]!=dic[b]:\n",
    "                edges[a].add(b)\n",
    "                edges[b].add(a)\n",
    "        #对每个联通分量求树的直径（两次bfs)\n",
    "        cmax=0\n",
    "        covered=set()\n",
    "        def diameter(i,covered):\n",
    "            covered.add(i)\n",
    "            #第一次bfs\n",
    "            queue=[i]\n",
    "            cover={i}\n",
    "            while queue:\n",
    "                tmp=[]\n",
    "                for node in queue:\n",
    "                    for neighbor in edges[node]:\n",
    "                        if neighbor not in cover:\n",
    "                            cover.add(neighbor)\n",
    "                            covered.add(neighbor)\n",
    "                            tmp.append(neighbor)\n",
    "                if tmp:\n",
    "                    queue=tmp\n",
    "                else:\n",
    "                    start_node=queue[0]\n",
    "                    break\n",
    "                    \n",
    "            #第二次bfs\n",
    "            queue=[start_node]\n",
    "            step=0\n",
    "            cover={start_node}\n",
    "            while queue:\n",
    "                tmp=[]\n",
    "                for node in queue:\n",
    "                    for neighbor in edges[node]:\n",
    "                        if neighbor not in cover:\n",
    "                            cover.add(neighbor)\n",
    "                            tmp.append(neighbor)\n",
    "                if tmp:\n",
    "                    queue=tmp\n",
    "                \n",
    "                if tmp==[]:\n",
    "                    return step+1,covered\n",
    "                step+=1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if i not in covered:\n",
    "                #开展含有i的联通分量的直径求解\n",
    "                t,s=diameter(i,set())\n",
    "                cmax=max(cmax,t)\n",
    "                covered|=s\n",
    "        return cmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        def lengths():\n",
    "            downs = [[0] for _ in s]\n",
    "            ts = TopologicalSorter({i: [j] for i, j in enumerate(parent)})\n",
    "            for node in [*ts.static_order()][:0:-1]:\n",
    "                yield 1 + sum(nlargest(2, downs[node]))\n",
    "                if s[node] != s[parent[node]]:\n",
    "                    downs[parent[node]].append(1 + max(downs[node]))\n",
    "        return max(lengths())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        self.children = [[] for i in range(len(parent))]\n",
    "        self.s = s\n",
    "        for i, p in enumerate(parent):\n",
    "            if p == -1: continue\n",
    "            self.children[p].append(i)\n",
    "\n",
    "        self.result = 0\n",
    "        self.traverse(0)\n",
    "        return self.result\n",
    "    def traverse(self, node):\n",
    "        r = (0, 0)\n",
    "        for child in self.children[node]:\n",
    "            x = self.traverse(child)\n",
    "            if self.s[node] == self.s[child]: continue\n",
    "            if x > r[0]:\n",
    "                r = (x, r[0])\n",
    "            elif x > r[1]:\n",
    "                r = (r[0], x)\n",
    "        self.result = max(self.result, r[0] + r[1] + 1)\n",
    "        return r[0] + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def dfs(self, now, s):\n",
    "        # print(now, self.chs[now])\n",
    "        for ch in self.chs[now]:\n",
    "            self.dfs(ch, s)\n",
    "            if s[now] != s[ch]:\n",
    "                self.ans[now] = max(self.ans[now], self.ans[ch] + 1)\n",
    "    \n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        self.chs = [[] for i in range(100005)]\n",
    "        self.ans = [1 for i in range(100005)]\n",
    "        N = len(parent)\n",
    "        for i in range(1,N):\n",
    "            self.chs[parent[i]].append(i)\n",
    "        self.dfs(0, s)\n",
    "        ret = 0\n",
    "#         for i in range(N):\n",
    "#             print(self.ans[i], end=' ')\n",
    "        \n",
    "        for i in range(N):\n",
    "            chans = []\n",
    "            for ch in self.chs[i]:\n",
    "                if s[ch] != s[i]:\n",
    "                    chans.append(self.ans[ch])\n",
    "                else:\n",
    "                    chans.append(0)\n",
    "            chans.sort()\n",
    "            if len(chans) >= 2:\n",
    "                ret = max(chans[-1] + chans[-2] + 1 , ret)\n",
    "            ret = max(self.ans[i], ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        res  = 0\n",
    "        def dfs(x, ans):\n",
    "          \n",
    "            max_len = 0\n",
    "            for y in g[x]:\n",
    "                len, ans = dfs(y, ans)\n",
    "                len = len +  1\n",
    "                if s[y] != s[x]:\n",
    "                    ans = max(ans, max_len + len)\n",
    "                    max_len = max(max_len, len)\n",
    "            return max_len, ans\n",
    "        _, res = dfs(0, 0)\n",
    "        return res + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        self.ans = 0\n",
    "        n = len(parent)\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            tree[parent[i]].append(i)\n",
    "        \n",
    "        def dfs(x=0):\n",
    "            x_len = 0\n",
    "            for y in tree[x]:\n",
    "                y_len = dfs(y) + 1\n",
    "                if s[x] != s[y]:\n",
    "                    self.ans = max(self.ans, x_len + y_len)\n",
    "                    x_len = max(x_len, y_len)\n",
    "            return x_len\n",
    "        \n",
    "        dfs()\n",
    "        return self.ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        T = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            T[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            max_len = 0\n",
    "            for y in T[x]:\n",
    "                len = dfs(y)+1\n",
    "                if s[y]!=s[x]:\n",
    "                    ans = max(ans, max_len+len)\n",
    "                    max_len = max(max_len,len)\n",
    "            return max_len\n",
    "        dfs(0)\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        res = 0\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "            g[i].append(parent[i])\n",
    "        def dfs(u, father):\n",
    "            nonlocal res\n",
    "            d1, d2 = 0, 0\n",
    "            for i in g[u]:\n",
    "                if i == father: continue\n",
    "                d = dfs(i, u) + 1\n",
    "                if s[i] != s[u]:\n",
    "                    if d > d1:\n",
    "                        d2 = d1\n",
    "                        d1 = d\n",
    "                    elif d > d2:\n",
    "                        d2 = d\n",
    "                    res = max(res, d1 + d2)\n",
    "            return d1\n",
    "        dfs(0, -1)\n",
    "        return res + 1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        ans = 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, v in enumerate(parent[1:]):  # i = actual index - 1\n",
    "            g[v].append(i + 1)\n",
    "\n",
    "        def dfs(cur):\n",
    "            if not g[cur]:\n",
    "                return 0\n",
    "            first, second = 0, 0\n",
    "            nonlocal ans\n",
    "            for val in g[cur]:  # child\n",
    "                temp = dfs(val) + 1\n",
    "                if s[cur] != s[val]:\n",
    "                    if temp >= first:\n",
    "                        first, second = temp, first\n",
    "                    elif temp > second:\n",
    "                        second = temp\n",
    "                    ans = max(ans, first + second +1)\n",
    "            return first\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        dic = {}\n",
    "        for i,pa in enumerate(parent):\n",
    "            if pa not in dic:\n",
    "                dic[pa]=[i]\n",
    "            else:\n",
    "                dic[pa].append(i)\n",
    "        res = 1\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root not in dic:\n",
    "                return 1\n",
    "            m1,m2 = 0,0\n",
    "            for child in dic[root]:\n",
    "                tmp = dfs(child)\n",
    "                if s[child]!=s[root]:\n",
    "                    if tmp>=m1:\n",
    "                        m1,m2 = tmp,m1\n",
    "                    elif m2<tmp<m1:\n",
    "                        m2 = tmp\n",
    "            res = max(m1+m2+1,res)\n",
    "            return m1+1\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        n = len(parent)\n",
    "        for i in range(n):\n",
    "            dic[parent[i]].append(i)\n",
    "        ans = 0\n",
    "        def dfs(v):\n",
    "            nonlocal ans\n",
    "            print(ans)\n",
    "            maxlen = 0\n",
    "            for u in dic[v]:\n",
    "                \n",
    "                l = dfs(u)+1\n",
    "                if s[u]!=s[v]:\n",
    "                    ans = max(ans,maxlen+l)\n",
    "                    maxlen = max(maxlen,l)\n",
    "            return maxlen\n",
    "        dfs(0)       \n",
    "        return ans+1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        G = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            G[parent[i]].append(i)\n",
    "\n",
    "        ans = 1\n",
    "        def dfs(i, p):\n",
    "            nonlocal ans\n",
    "            length = [0]\n",
    "            for j in G[i]:\n",
    "                if j == p: continue\n",
    "                l = dfs(j, i)\n",
    "                if s[j] != s[i]:\n",
    "                    length.append(l)\n",
    "            length.sort(reverse=True)\n",
    "            ans = max(ans, sum(length[:2])+1)\n",
    "            return length[0] + 1\n",
    "\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, len(parent)):\n",
    "            graph[parent[i]].append(i)\n",
    "        class info:\n",
    "            def __init__(self, maxpath, maxpath1):\n",
    "                self.maxpath = maxpath\n",
    "                self.maxpath1 = maxpath1\n",
    "        def f(u):\n",
    "            if len(graph[u]) == 0:\n",
    "                return info(1, 1)\n",
    "            maxpath = 1\n",
    "            max1 = 0\n",
    "            max2 = 0\n",
    "            for v in graph[u]:\n",
    "                infonext = f(v)\n",
    "                maxpath = max(maxpath, infonext.maxpath)\n",
    "                if s[u] != s[v]:\n",
    "                    if infonext.maxpath1 > max1:\n",
    "                        max2 = max1\n",
    "                        max1 = infonext.maxpath1\n",
    "                    elif infonext.maxpath1 > max2:\n",
    "                        max2 = infonext.maxpath1\n",
    "            maxpath = max(maxpath, max1+max2+1)\n",
    "            maxpath1 = max1 + 1\n",
    "            return info(maxpath, maxpath1)\n",
    "        return f(0).maxpath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n=len(s)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        graph[0].append(-1)\n",
    "        for i in range(1,n):\n",
    "            graph[parent[i]].append(i)\n",
    "            graph[i].append(parent[i])\n",
    "        print(graph)\n",
    "        ans=1\n",
    "        #建树完成\n",
    "        def dfs(x,fa):\n",
    "            nonlocal ans\n",
    "            #叶子节点\n",
    "            if len(graph[x])==1:\n",
    "                return 1\n",
    "            dp=0\n",
    "            res=[0,0]\n",
    "            #本质还是要在子树找两条最长的路径\n",
    "            for y in graph[x]:\n",
    "                if y==fa: continue\n",
    "                nex=dfs(y,x)\n",
    "                #状态转移\n",
    "                if s[x]!=s[y]:\n",
    "                    if nex>res[1]:\n",
    "                        res[0]=res[1]\n",
    "                        res[1]=nex\n",
    "                    elif nex>res[0]:\n",
    "                        res[0]=nex\n",
    "            if res[1]>0:\n",
    "                dp=res[1]+1\n",
    "            else:\n",
    "                dp=1\n",
    "            ans=max(ans,res[0]+res[1]+1)\n",
    "            return dp\n",
    "        dfs(0,-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if s[i] != s[parent[i]]:\n",
    "                g[i].append(parent[i])\n",
    "                g[parent[i]].append(i)\n",
    "\n",
    "        visit = 0\n",
    "\n",
    "        def dfs(now, father, dist):\n",
    "            nonlocal visit\n",
    "            visit |= (1 << now)\n",
    "            if len(g[now]) == 1 and g[now][0] == father:\n",
    "                return 1, dist\n",
    "            max1, max2 = -inf, -inf\n",
    "            maxa = -inf\n",
    "            for nex in g[now]:\n",
    "                if nex != father:\n",
    "                    a, b = dfs(nex, now, dist+1)\n",
    "                    if b > max1:\n",
    "                        max2, max1 = max1, b\n",
    "                    elif b > max2:\n",
    "                        max2 = b\n",
    "                    maxa = max(a, maxa)\n",
    "            return max(maxa, max1+max2-2*dist+1), max1\n",
    "\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            if not visit & (1 << i):\n",
    "                a, b = dfs(i, -1, 1)\n",
    "                res = max(res, a, b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        child = defaultdict(list)\n",
    "        for i,x in enumerate(parent):\n",
    "            child[x].append(i)\n",
    "        ans = 1\n",
    "\n",
    "        def dfs(node):\n",
    "            # return 以node为root的最长路径\n",
    "            if not child[node]: return 1\n",
    "            lens = []\n",
    "            for c in child[node]:\n",
    "                _len = dfs(c)\n",
    "                if s[c] != s[node]:\n",
    "                    lens.append(_len)\n",
    "            if lens:\n",
    "                lens.sort(key=lambda x:-x)\n",
    "                nonlocal ans\n",
    "                ans = max(ans, sum(lens[:2]) + 1)\n",
    "                return lens[0] + 1\n",
    "            return 1\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = defaultdict(list)\n",
    "        for i, x in enumerate(parent):\n",
    "            g[x].append(i)\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        def dfs(u: int) -> int:\n",
    "            nonlocal ans\n",
    "            res = 1\n",
    "            sub = [0, 0]  # 加2个0，是为了后面逻辑判断代码简单点\n",
    "            for v in g[u]:\n",
    "                size = dfs(v)\n",
    "                if s[u] != s[v]:\n",
    "                    sub.append(size)\n",
    "            sub.sort(reverse=True)\n",
    "            mx = res + sub[0] + sub[1]  # 自身加最长的两个孩子\n",
    "            if mx > ans:\n",
    "                ans = mx\n",
    "            return res + sub[0]  # 自身加最长的一个孩子\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        child = defaultdict(list)\n",
    "        for i,p in enumerate(parent[1:], start=1):\n",
    "            child[p].append(i)\n",
    "        # print(child)\n",
    "\n",
    "        pathlen = defaultdict(list)\n",
    "        def path(i):\n",
    "            if not child[i]:\n",
    "                return [0]\n",
    "            for j in child[i]:\n",
    "                if s[i] == s[j]:\n",
    "                    pathlen[i].append(0)\n",
    "                    path(j)\n",
    "                else:\n",
    "                    pathlen[i].append(1 + max(path(j)))\n",
    "            return pathlen[i]\n",
    "\n",
    "        path(0)\n",
    "        # print(pathlen)\n",
    "\n",
    "        ans = 1\n",
    "        for i,v in pathlen.items():\n",
    "            if len(v) == 1:\n",
    "                ans = max(ans, 1+v[0])\n",
    "            else:\n",
    "                # v.sort(reverse=True)\n",
    "                v = heapq.nlargest(2,v)\n",
    "                ans = max(ans, 1+v[0]+v[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        e = defaultdict(set)\n",
    "        for i in range(1,n):\n",
    "            fa = parent[i]\n",
    "            e[fa].add(i)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        \n",
    "        ans = 1\n",
    "        def dfs(cur):\n",
    "            nonlocal dp,e,ans\n",
    "            for nxt in e[cur]:\n",
    "                dfs(nxt)\n",
    "            mv1,mv2 = -float('inf'),-float('inf')\n",
    "            for nxt in e[cur]:\n",
    "                if s[nxt] != s[cur]:\n",
    "                    if dp[nxt] > mv1:\n",
    "                        mv2,mv1 = mv1,dp[nxt]\n",
    "                    elif dp[nxt] > mv2:\n",
    "                        mv2 = dp[nxt]\n",
    "            if mv1 == -float('inf'):\n",
    "                dp[cur] = 1\n",
    "            elif mv2 == -float('inf'):\n",
    "                dp[cur] = max(dp[cur],1 + mv1)\n",
    "                ans = max(ans,1 + mv1)\n",
    "            else:\n",
    "                dp[cur] = max(dp[cur],1 + mv1)\n",
    "                ans = max(ans,1 + mv1 + mv2)\n",
    "            return\n",
    "        dfs(0)\n",
    "    \n",
    "        return ans\n",
    "               \n",
    "                \n",
    "            \n",
    "                        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        e = defaultdict(set)\n",
    "        for i in range(1,n):\n",
    "            fa = parent[i]\n",
    "            e[fa].add(i)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        \n",
    "        ans = 1\n",
    "        def dfs(cur):\n",
    "            nonlocal dp,e,ans\n",
    "            for nxt in e[cur]:\n",
    "                dfs(nxt)\n",
    "            v = []\n",
    "            for nxt in e[cur]:\n",
    "                if s[nxt] != s[cur]:\n",
    "                    v.append(dp[nxt])\n",
    "            v.sort(reverse = True)\n",
    "            \n",
    "          \n",
    "            if not v:\n",
    "                dp[cur] = 1\n",
    "            elif len(v) < 2:\n",
    "                dp[cur] = max(dp[cur],1 + v[0])\n",
    "                ans = max(ans,1 + v[0])\n",
    "            else:\n",
    "                dp[cur] = max(dp[cur],1 + v[0])\n",
    "                ans = max(ans,1 + v[0] + v[1])\n",
    "            return\n",
    "        dfs(0)\n",
    "    \n",
    "        return ans\n",
    "               \n",
    "                \n",
    "            \n",
    "                        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "相邻字符不同的最长路径\n",
    "非换根dp 就是树形dp\n",
    "'''\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        #先建立grid\n",
    "        n = len(parent)\n",
    "        grid = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            grid[parent[i]].append(i)\n",
    "\n",
    "        #先自底向上，求出在以0节点为根的，以各个节点为子树根节点的子树的最长路径\n",
    "        fise = [[1, 1] for i in range(n)]  #第1长，第2长（次长）\n",
    "        def dfs(cur):\n",
    "            for nxt in grid[cur]:\n",
    "                dfs(nxt)    \n",
    "                if s[cur] == s[nxt]:   #还是要计算的啊                       \n",
    "                    continue\n",
    "\n",
    "                if fise[nxt][0] + 1 >= fise[cur][0]:\n",
    "                    fise[cur][1] = fise[cur][0]\n",
    "                    fise[cur][0] = fise[nxt][0] + 1\n",
    "                elif fise[nxt][0] + 1 > fise[cur][1]:\n",
    "                    fise[cur][1] = fise[nxt][0] + 1\n",
    "\n",
    "        #自顶向下，换根dp\n",
    "        up = [0] * n     #往上不包括子树走的最长路径\n",
    "        ans = [0] * n\n",
    "        def dfs1(cur):\n",
    "            #print(cur)\n",
    "            if cur == 0:\n",
    "                up[cur] = 1\n",
    "                ans[cur] = fise[0][0] + fise[0][1] - 1\n",
    "            else:\n",
    "                ans[cur] = fise[cur][0] + fise[cur][1] - 1\n",
    "                if s[parent[cur]] != s[cur]:\n",
    "                    if fise[cur][0] + 1 < fise[parent[cur]][0]:\n",
    "                        up[cur] = max(up[parent[cur]], fise[parent[cur]][0]) + 1\n",
    "                    else:\n",
    "                        up[cur] = max(up[parent[cur]], fise[parent[cur]][1]) + 1\n",
    "                    ans[cur] = max(ans[cur], up[cur] + fise[cur][0] - 1)\n",
    "\n",
    "            for nxt in grid[cur]:\n",
    "                dfs1(nxt)\n",
    "        \n",
    "        dfs(0)\n",
    "        dfs1(0)\n",
    "        \n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        edges = defaultdict(set)\n",
    "        for i in range(1, len(parent)):\n",
    "            edges[parent[i]].add(i)\n",
    "        \n",
    "        # print(edges)\n",
    "        \n",
    "        def dfs(u):\n",
    "            ans = 1\n",
    "            lens = [0, 0]\n",
    "            for v in edges[u]:\n",
    "                mAns, mLen = dfs(v)\n",
    "                ans = max(ans, mAns)\n",
    "                if s[v] != s[u]:\n",
    "                    if mLen > lens[0]:\n",
    "                        lens[1] = lens[0]\n",
    "                        lens[0] = mLen\n",
    "                    elif mLen > lens[1]:\n",
    "                        lens[1] = mLen\n",
    "            return max(ans, lens[0] + lens[1] + 1), lens[0] + 1\n",
    "        \n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for i, p in enumerate(parent):\n",
    "            g[p].add(i)\n",
    "        g.pop(-1)\n",
    "\n",
    "        def DFS(x):\n",
    "            if len(g[x]) == 0:\n",
    "                return 1\n",
    "            arr = [0, 0]\n",
    "            for y in g[x]:\n",
    "                t = DFS(y)\n",
    "                if s[x] != s[y]:\n",
    "                    # 只保留最大的两个\n",
    "                    arr = sorted(arr + [t])[-2:]\n",
    "            nonlocal ans\n",
    "            ans = max(ans, 1 + sum(arr))\n",
    "            return 1 + arr[-1]\n",
    "\n",
    "        ans = int(len(s) > 0)\n",
    "        DFS(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#可能需要搭配手写栈板子，仅适合1e5及以下数据\n",
    "import bisect\n",
    "class Dfstreemono:\n",
    "    def __init__(self,edges,price):#顶点数量，边\n",
    "        n = len(edges)+1\n",
    "        self.price = price\n",
    "        self.nums = [[] for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            self.nums[i].append(j)\n",
    "            self.nums[j].append(i)\n",
    "        for i in range(n):\n",
    "            self.nums[i].sort()\n",
    "        self.pre = [[0]*(len(self.nums[x])+1) for x in range(n)]\n",
    "        self.suf = [[0]*(len(self.nums[x])+1) for x in range(n)]\n",
    "        self.has = [{} for _ in range(n)]\n",
    "        self.used = [-1]*n\n",
    "    def build(self,node):\n",
    "        lst = [self.has[node][x] for x in self.nums[node]]\n",
    "        m = len(lst)\n",
    "        for i in range(m):\n",
    "            self.pre[node][i+1] = max(self.pre[node][i],lst[i])\n",
    "        for i in range(m-1,-1,-1):\n",
    "            self.suf[node][i] = max(self.suf[node][i+1],lst[i])\n",
    "    def dfs(self,node,pre):\n",
    "        if node != pre and self.price[node] == self.price[pre]:return 0\n",
    "        res = 0\n",
    "        if self.used[node] == -1:#-1未遍历，相等已经遍历完了，否则一个节点未遍历\n",
    "            for i in self.nums[node]:\n",
    "                if i != pre:\n",
    "                    self.has[node][i] = self.dfs(i,node)\n",
    "                    res = max(res,self.has[node][i])\n",
    "            if pre == node:self.build(node)\n",
    "            self.used[node] = pre\n",
    "        else:\n",
    "            if self.used[node] != node:\n",
    "                self.has[node][self.used[node]] = self.dfs(self.used[node],node)\n",
    "                self.build(node)\n",
    "                self.used[node] = node\n",
    "            if pre != node:\n",
    "                idx = bisect.bisect_left(self.nums[node],pre)\n",
    "                res = max(self.pre[node][idx], self.suf[node][idx + 1])\n",
    "            else:\n",
    "                res = self.suf[node][0]\n",
    "        return res+1\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        edges = []\n",
    "        n = len(parent)\n",
    "        for i in range(n):\n",
    "            if parent[i] == -1:continue\n",
    "            edges.append((i,parent[i]))\n",
    "        dfst = Dfstreemono(edges,s)\n",
    "        return max(dfst.dfs(i,i) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, x in enumerate(parent):\n",
    "            if s[u] != s[x] and u > 0:\n",
    "                g[x].append(u)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            max_len = 0\n",
    "            for y in g[x]:\n",
    "                sub_len = dfs(y) + 1\n",
    "                nonlocal ans\n",
    "                ans = max(ans, max_len + sub_len)\n",
    "                max_len = max(max_len, sub_len)\n",
    "            return max_len\n",
    "        for i in parent:\n",
    "            dfs(i)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPath(self, parent: List[int], s: str) -> int:\n",
    "        n = len(parent)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            g[parent[i]].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            x_len = 0\n",
    "            for y in g[x]:\n",
    "                y_len = dfs(y) + 1\n",
    "\n",
    "                if s[y] != s[x]:\n",
    "                    ans = max(ans, x_len + y_len)\n",
    "                    x_len = max(x_len, y_len)\n",
    "\n",
    "            return x_len\n",
    "\n",
    "        dfs(0)\n",
    "        return ans + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
